package com.排序.交换.冒泡;

import java.util.Arrays;

/**
 * the class of algorithm
 *
 * 核心思想是：
 *
 * 使用双重循环
 * 内循环把最大的数移动到最后位置(次数)，外循环表示需要移动的元素个数（轮数）
 * <p>
 * .
 *
 * @author little_lunatic
 * @date 2022-12-09
 */
public class MP {
    public static void main(String[] args) {
        int[] arr = new int[]{1, 3, 2, 5, 4, 0};
        mpSort(arr);
        System.out.println(Arrays.toString(arr));

        int[] arr2 = new int[]{1, 2, 2, 5, 4};
        mpSortPlus1(arr2);
        System.out.println(Arrays.toString(arr2));
    }


    /**
     * 1.未优化冒泡排序
     * @param arr
     */
    private static void mpSort(int[] arr){
        if(arr == null) {
            throw new NullPointerException();
        }
        if(arr.length <= 1) {
            return;
        }

        int temp;
        for (int i = 0; i < arr.length - 1; i++) {
            // 下一次外循环，比较的数组长度 -i。因为需要把最大的放到队尾，队尾的就不需要参与下一次的排序了。
            for (int j = 0; j < arr.length - 1 - i; j++) {
                if (arr[j] > arr[j + 1]){
                    temp = arr[j];
                    arr[j] = arr[j+1];
                    arr[j+1] = temp;
                }
            }
        }
    }


    /**
     * 2.优化轮数
     * 加入标志位，表示是相邻位置否交换过
     * @param arr
     */
    private static void mpSortPlus1(int[] arr){
        if(arr == null) {
            throw new NullPointerException();
        }
        if(arr.length <= 1) {
            return;
        }

        int temp;
        for (int i = 0; i < arr.length - 1; i++) {
            boolean flag = false;
            // 下一次外循环，比较的数组长度 -i。因为需要把最大的放到队尾，队尾的就不需要参与下一次的排序了。
            for (int j = 0; j < arr.length - 1 - i; j++) {
                if (arr[j] > arr[j + 1]){
                    temp = arr[j];
                    arr[j] = arr[j+1];
                    arr[j+1] = temp;
                    flag = true;
                }
            }
            // 如果这一轮没有交换过元素，则表示当前数组已经是一个有序数组了，跳出循环
            if (!flag){
                System.out.println("\n第 " + (i+1) + " 轮排序时，剩下的元素已经是一个有序数组了，跳出循环");
                break;
            }
        }
    }


}
